package editor.cn;

import java.text.DateFormatSymbols;

class Solution1143{
    public static void main(String[] args) {
        Solution solution = new Solution1143().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
    //    如何破题？既然是最长公共子序列，那么先求出较小的串的所有子序列，然后套在大的里面看看有没有就行了，从长倒短开始套
        int lenMin=Math.min(text1.length(),text2.length());
        //那就要求出短串的所有子序列，这太长了，范围在1000呢，不可能是正解
        //会不会是哈希表，长的先铺成数组，之后短的再在上面递减，这样也不行。找不到具体在哪里。
        //只有dp了。dp[i][j]表示截止text1的长度为i，text2长度为j的最长公共子串的长度。
        char[] charArray1 = text1.toCharArray();
        char[] charArray2 = text2.toCharArray();
        int len1=charArray1.length;
        int len2=charArray2.length;
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                dp[i+1][j+1]=charArray1[i]==charArray2[j]?dp[i][j]+1:Math.max(dp[i+1][j],dp[i][j+1]);
            }
        }
        return dp[len1][len2];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}












